package Top200;

/**
 * @author zhangmin
 * @create 2022-02-21 15:05
 * 1、滑动窗口
 * 2、dp：dp[i]表示以i为结尾的最长有效括号字串长度
 * 当s[i]==‘）’时，若s[i-1]=='('，则为。。。（）的形式，dp[i]=dp[i-2]+2;
 *                若s[i-1]==')',则为。。。））的形式，判断s[i-dp[i-1]-1]==‘（’，dp[i]=dp[i-dp[i-1]-2]+dp[i-1]+2;
 */
public class longestValidParentheses32 {
    public int longestValidParentheses(String s) {
        int n=s.length();
        if (n<=1) return 0;
        int[] dp=new int[n];
        dp[0]=0;
        int res=0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i)==')'){
                if (s.charAt(i-1)=='('){
                    dp[i]=dp[i-2]+2;
                }else if (s.charAt(i-1)==')'&&s.charAt(i-dp[i-1]-1)=='('){
                    dp[i]=dp[i-1]+((i-dp[i-1]-2>=0)?dp[i-dp[i-1]-2]:0)+2;
                }
                res= Math.max(res,dp[i]);
            }
        }
        return res;
    }
}
